/*
 * Created on 3 Sep 2007
 *
 * Copyright (c) 2006 P.J.Leonard
 * 
 * http://www.frinika.com
 * 
 * This file is part of Frinika.
 * 
 * Frinika is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.

 * Frinika is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.

 * You should have received a copy of the GNU General Public License
 * along with Frinika; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */
package model;

import java.util.HashSet;
import java.util.Vector;

import model.Board.Move;

public class DepthFirstSearch implements Search {

    Board board;
    HashSet<Long> visited = new HashSet<Long>();

    public DepthFirstSearch(Board board) {
        this.board = board;
    }

    public int explore() {

        Vector<Board.Move> moves = new Vector<Board.Move>(board.getMoves());
        
        for (Board.Move move : moves) { // For all legal moves

            move.doMove();                       // do the move

            if (display) {    // Cosmetics
                board.notifyObservers();
            }

            if (board.hasWon()) {
                return WIN;     // Hooray
            }

            Long boardKey = board.longHashCode(); // grab the board state

            if (!visited.contains(boardKey)) {    // ignore if already visited
                visited.add(boardKey);            // keep a record
                if (explore() == WIN) {
                    return WIN; // otherwise start again from new pos.
                }
            }

            board.undo();                         // go back to previous state


            if (display) {    // Cosmetics
                board.notifyObservers();
            }

        }
        return FAIL;
    }
}
